/** list.d
  Written in the D programming language 1.0

Authors:
	Wei Li (oldrev@gmail.com)

Copyright:	Copyright (C) 2007 Wei Li.
License:	BSD

*/

module dotmars.base.collection.list;

import dotmars.base.collection.container;
import dotmars.base.iterator;
import dotmars.base.algorithms;
import dotmars.base.stdtypes;
import dotmars.base.allocation;

////////////////////////////////////////////////////////////////////////////////


////////////////////////////////////////

// List 类的迭代器基模板
private template ListIteratorBase(ListCont)
{
	public const TraversalCategory	TraversalTag = TraversalCategory.Bidirectional;
	public const AccessCategory		AccessTag = AccessCategory.Lvalue;

	public alias ListCont ContainerType;
	public alias ListCont.ValueType ValueType;
	public alias ListCont.PtrType PtrType;
	private alias ListCont.Node Node;

	private Node   m_node = null;

	private Node node() {
		return m_node;
	}

	public static SelfType opCall(SelfType i)
	{
		SelfType ret;
		ret.m_node = i.m_node;
		return ret;
	}

	private static SelfType opCall(Node p)
	{
		SelfType i;
		i.m_node = p;
		return i;
	}

	public PtrType ptr() 
	in {
		assert(m_node !is null);
	}
	body {
		return m_node.valuePtr;
	}

	public ValueType value()
	in {
		assert(m_node !is null);
	}
	body {
		return m_node.value;
	}

	public void value(ValueType v) 
	in {
		assert(m_node !is null);
	}
	body {
		m_node.value = v;
	}

	void swap(ref SelfType rhs) {
		.swap(rhs.m_node, this.m_node);
	}

	SelfType opPostInc() //i++ {
	{
		SelfType i = *this;
		moveNext();
		return i;
	}

	SelfType opPostDec() // i-- 
	{
		SelfType i = *this;
		movePrevious();
		return i;
	}

	bool opEquals(SelfType rhs) { // a == b 
		return rhs.m_node is m_node;
	}

	SelfType opAddAssign(ptrdiff_t n) { // += {
		while(n-- != 0) moveNext();
		return *this;
	}
			
	SelfType opSubAssign(ptrdiff_t n) { //-=
		while(n-- != 0) movePrevious();
		return *this;
	}
}

////////////////////////////////////////////////////////////////////////////////

private struct ListIterator(ListCont)
{
	alias ListIterator!(ListCont) SelfType;

	mixin ListIteratorBase!(ListCont);

	private void moveNext() {
		m_node = m_node.next;                
	}

	private void movePrevious() {
		m_node = m_node.prev;
	}
}

////////////////////////////////////////////////////////////////////////////////

private struct ListReverseIterator(ListCont)
{
	alias ListReverseIterator!(ListCont) SelfType;

	mixin ListIteratorBase!(ListCont);

	private void moveNext() {
		m_node = m_node.prev;
	}

	private void movePrevious() {
		m_node = m_node.next;
	}
}

////////////////////////////////////////////////////////////////////////////////

class List(EleType, alias AllocatorT = DefaultGCAllocator) : ICloneable
{
	//alias:
	public alias EleType		ValueType;
	public alias EleType*		PtrType;
	public alias typeof(this)	SelfType;
	public alias ListIterator!(SelfType)		Iterator;
	public alias ListReverseIterator!(SelfType)	ReverseIterator;

	//mixins:
	private mixin AllocatorT!();
    mixin OpApplyAspect!(SelfType);
    mixin OpApplyReverseAspect!(SelfType);

	//inner class:
	private class Node
	{
		private ValueType m_value;
		private Node m_prev;
		private Node m_next;

		static new(size_t bytes)
		{
			return allocate(bytes);
		}

		delete(void* p)
		{
			deallocate(p);
		}

		public this() {
			m_prev = null;
			m_next = null;
			m_value = ValueType.init;
		}

		public this(ValueType val)
		{
			m_prev = null;
			m_next = null;
			m_value = val;
		}

		public this(Node m, Node n, ValueType val) 
		{
			m_prev = m;
			m_next = n;
			m_value = val;

			if(m !is null) m.next = this;
			if(n !is null) n.prev = this;
		}

		public Node prev() {
			return m_prev;
		}

		public void prev(Node n) {
			m_prev = n;
		}

		public void next(Node n) {
			m_next = n;
		}

		public Node next() {
			return m_next;
		}

		public ValueType value() {
			return m_value;
		}

		public void value(ValueType v) {
			m_value = v;
		}

		public PtrType valuePtr() {
			return &m_value;
		}

		public static void join(Node first, Node second)            
		in {
			assert(first !is null);
			assert(second !is null);
		}
		body {
			first.next = second;
			second.prev = first;
		}
	}

	//fields:

	private Node m_head = null;
	private Node m_tail = null;
	private size_t m_length = 0;

	public alias clone dup; 

	// Container aspects:
	mixin OpCatAssignAspect!(SelfType);

	public this()
	{
		m_head = null;
		m_tail = null;
		m_length = 0;
	}

	public this(Iterator ifirst, Iterator ilast) {
		for(; ifirst != ilast; ++ifirst)
			addLast(ifirst.value);
	}

	public this(ReverseIterator ifirst, ReverseIterator ilast) {
		for(; ifirst != ilast; ++ifirst)
			addLast(ifirst.value);
	}

	public this(ValueType val, size_t count) {
		for(size_t i = 0; i < count; ++i)
			addLast(val);
	}

	public ~this() {
		clear(); 
	}

	public override SelfType clone() {
		return new SelfType(this.begin(), this.end());
	}

	public Iterator begin() {
		return Iterator(m_head);	
	}

	public Iterator end() {
		return Iterator(null);
	}

	public ReverseIterator rbegin() {
		return ReverseIterator(m_tail);
	}

	public ReverseIterator rend() {
		return ReverseIterator(null);
	}

	public ValueType first() {
		assert(!empty);
		return m_head.value;
	}

	public ValueType last() {
		assert(!empty);
		return m_tail.value;
	}

	public bool empty() {
		return m_length == 0; 
	}

	public void clear() 
	{
		if(empty)return;
		remove(begin(), end());
		m_head = null;
		m_tail = null;
	}

	public Iterator remove(Iterator where)
	in {
		assert(where != end);
	}
	body {
		Node n = where.m_node;
		Iterator ret = Iterator(n.next);

		if(n.prev !is null) n.prev.next = n.next;
		if(n.next !is null) n.next.prev = n.prev;

		delete n;
		n = null;
		m_length--;
		return ret;
	}

	public Iterator remove(Iterator ifirst, Iterator ilast)
	in {
		assert(ifirst != end);
	}
	body {
		Iterator i = ifirst;
		while(i != ilast)
			i = remove(i);
		return i;
	}

	public void addFirst(ValueType val)
	{
		Node n = new Node(null, m_head, val);
		if(empty) m_tail = n; 
		m_head = n;
		m_length++;
	}

	public void addLast(ValueType val)
	{
		Node n = new Node(m_tail, null, val);
		if(empty) m_head = n;
		m_tail = n;
		m_length++;
	}

	public void removeFirst() {
		assert(!empty);
		remove(Iterator(m_head));
	}

	public void removeLast() {
		assert(!empty);
		remove(Iterator(m_tail));
	}

    public Iterator addBefore(Iterator where, ValueType val)
	in {
        assert(where != end);
	}
	body {
        Node newNode = new Node(where.node.prev, where.node, val);
		m_length++;
        return Iterator(newNode);
    }

    public void addRangeBefore(IterType)(Iterator where, IterType ifirst, IterType ilast)
	in {
		static assert(is(IterType.ValueType : ValueType));
		assert(where != end);
	}
	body {
        IterType i = ifirst;
        Iterator pos = where;
        while(i != ilast) {
            pos = addBefore(pos, i.value);
            ++i;
        }
    }

    public Iterator addAfter(Iterator where, ValueType val)
	in {
		assert(where != end);
	}
	body {
		Node newNode = new Node(where.node, where.node.next, val);
		m_length++;
        return Iterator(newNode);
    }

    public void addRangeAfter(IterType) (Iterator where, IterType ifirst, IterType ilast)
	in {
		static assert(is(IterType.ValueType : ValueType));
		assert(where != end);
	}
	body {
        IterType i = ifirst;
        Iterator pos = where;
        while(i != ilast) {
            pos = addAfter(pos, i.value);
            ++i;
        }
    }

	public void swap(SelfType rhs)
	{
		.swap(rhs.m_head, m_head);
		.swap(rhs.m_tail, m_tail);
		.swap(rhs.m_length, m_length);
	}

}
